//搜索二维矩阵
//https://leetcode.cn/problems/search-a-2d-matrix/description/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) 
    {
        //在第一列二分找，返回小于target的最大值
        int n = matrix.size();
        int left = 0, right = n - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if(matrix[mid][0] <= target) left = mid;
            else right = mid - 1;
        } 
        if(matrix[left][0] == target) return true;  
        int row = left;

        //在left行找，返回小于等于target最右边的值
        left = 0; right = matrix[0].size() - 1;
        while(left < right)
        {
            int mid = left + (right - left + 1) / 2;
            
            if(matrix[row][mid] <= target) left = mid;
            else right = mid - 1;
        }
        if(matrix[row][left] == target) return true;  
        return false;
    }
};